/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
	ListNode* ReverseList(ListNode* head){
		if (NULL == head || NULL == head->next){
			return head;
		}
		ListNode* back = NULL;
		ListNode* cur = head;
		ListNode* prev = head;
		while (cur != NULL)
		{
			prev = cur->next;
			if (NULL == prev){
				head = cur;
			}
			cur->next = back;
			back = cur;
			cur = prev;
		}
		return head;
	}

	bool chkPalindrome(ListNode* A) {
		if (NULL == A || NULL == A->next){
			return true;
		}
		ListNode* fast = A;
		ListNode* slow = A;
		ListNode* prev = NULL;
		//1.找到链表中间节点
		while (fast && fast->next){
			fast = fast->next->next;
			prev = slow;
			slow = slow->next;
		}
		ListNode* mid = NULL;
		if (fast){          //fast != NULL说明奇数个节点
			mid = slow;
		}
		else{
			mid = prev;
		}

		//2.将原链表按中间节点分成两个新链表l1,l2
		ListNode* l1 = A;
		ListNode* l2 = mid->next;
		mid->next = NULL;

		//3.反转后半部分链表
		l2 = ReverseList(l2);

		//3.遍历比较两链表各节点val
		ListNode* cur1 = l1;
		ListNode* cur2 = l2;
		bool flag = true;
		while (cur1 && cur2)
		{
			if (cur1->val != cur2->val){
				flag = false;
				break;
			}
			cur1 = cur1->next;
			cur2 = cur2->next;
		}

		//4.还原原链表
		l2 = ReverseList(l2);
		mid->next = l2;

		return flag;
	}
};